home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / interp11.zip / INTERP.C next >
Text File  |  1991-10-14  |  17KB  |  671 lines
  1. /*
  2.  *
  3.  * INTERP.C  - An arithmetic expression interpreter in ANSI C.
  4.  *
  5.  * Written September, 1991 by Jonathan Guthrie and placed in the public domain
  6.  *
  7.  */
  8.  
  9. /*
  10.  * History:
  11.  *
  12.  * 10/14/1991 Jonathan R. Guthrie
  13.  * Revision 1.1:  Changed definition of number to suit Bob Stout
  14.  * better.  Also, changed the way I handle errors to match ANSI's
  15.  * specification of setjmp.
  16.  *
  17.  * 9/24/1991 Jonathan R. Guthrie
  18.  * Revision 1.0:  Original release
  19.  *
  20.  */
  21.  
  22. #include    <setjmp.h>
  23. #include    <stdlib.h>
  24. #include    <ctype.h>
  25. #include    <float.h>
  26. #include    <math.h>
  27.  
  28. #ifdef  DEBUG
  29. #include    <stdio.h>
  30. #endif  /* DEBUG */
  31.  
  32. #include    "interp.h"
  33.  
  34. /*
  35. This is the EBNF grammar of the language handled by the interpreter.
  36.  
  37. NOTE:  What I'm calling a number is slightly different from what C
  38. calls a float.  I did this to make the number recognizer easier to
  39. write.
  40.  
  41. expression = factor {("+"|"-") factor}.
  42. factor = power {("*"|"/") power}.
  43. power = {value "^"} value.
  44. value = number | ("(" expression ")") | ("+"|"-" value).
  45. number = (digit {digit} ["." {digit}])|("." digit {digit})
  46.         [("E"|"e") ["+"|"-"] digit {digit}].
  47.  
  48. Implementation:  The evaluator is implemented as a recursive
  49. evaluator. I did this because recursive evaluators are straightforward
  50. to code and simple to explain.  Basically, each one of the productions
  51. above, except for number, has a function.  If a production involves a
  52. nonterminal (a nonterminal is something that appears on the left side of
  53. a production) then the function handling the production calls the
  54. function that handles the nonterminal's production.  Terminals (quoted
  55. strings, in the grammar) and numbers are handled by gettoken.
  56.  
  57. Numbers are handled differently because recognizing a number is more
  58. properly the domain of a lexical analyzer than a parser.  Basically,
  59. I only include the numbers in the grammar in order to show what _I_
  60. am calling a number.  In the code, numbers are treated as terminals.
  61. */
  62.  
  63. #define PAREN       0x8000
  64. #define RPAREN      0x4000
  65. #define UNARY       0x2000
  66. #define POWER       0x1000
  67. #define MULTOP      0x0800
  68. #define ADDOP       0x0400
  69. #define NUMBER      0x0200
  70. #define ERROR       0x0100
  71.  
  72. #define ISPAREN(x)  ((x) & PAREN)
  73. #define ISUNARY(x)  ((x) & UNARY)
  74. #define ISPOWER(x)  ((x) & POWER)
  75. #define ISMULTOP(x) ((x) & MULTOP)
  76. #define ISADDOP(x)  ((x) & ADDOP)
  77. #define ISNUMBER(x) ((x) & NUMBER)
  78.  
  79. #define LPAREN      PAREN
  80. #define UNPLUS      UNARY
  81. #define UNMINUS     UNARY + 1
  82. #define STAR        MULTOP
  83. #define SLASH       MULTOP + 1
  84. #define PLUS        ADDOP
  85. #define MINUS       ADDOP + 1
  86.  
  87. typedef struct
  88. {
  89.     unsigned    type;
  90.     double      value;
  91. }   TOKEN;
  92.  
  93. #ifndef TRUE
  94. #define TRUE        1
  95. #endif
  96.  
  97. #ifndef FALSE
  98. #define FALSE       0
  99. #endif
  100.  
  101. /*
  102.  * For error handling by longjmp()
  103.  */
  104. static jmp_buf  error;
  105. static int      errortype;
  106.  
  107. /*
  108.  * To avoid needing an unget().
  109.  */
  110. static TOKEN    old_token;
  111.  
  112. /*
  113.  * To avoid passing input_func back and forth.
  114.  */
  115. static int  (*input_func)(void);
  116.  
  117. /*
  118.  * I need this one prototype because expression is called recursively
  119.  */
  120. static void expression(TOKEN *out);
  121.  
  122. /*
  123.  * It's just a big size.  Numbers are limited to no more than 100 characters
  124.  * long.  NOTE:  The length is checked to prevent buffer overruns.
  125.  */
  126. #define BUFFLEN     100
  127.  
  128. /*
  129.  * getnumber() recognizes a number in the input stream.  The number is
  130.  * returned in value, the first character of the number is passed in
  131.  * pushback which also passes back the first character after the number.
  132.  *
  133.  * getnumber() returns a status code which tells whether the number is
  134.  * ill-formed or not.
  135.  *
  136.  * Implementation:  getnumber() is coded as a deterministic finite-state-
  137.  * machine with six states.  State 0 is the start state, and state 5 is
  138.  * the end state.  Each state gets a case in the main switch statement.
  139.  * The cases are explained as they appear.
  140.  */
  141. static int  getnumber(double *value, int *pushback)
  142. {
  143. int     i, c, state, error;
  144. char    buff[BUFFLEN];
  145.  
  146.     i = error = 0;
  147.     c = buff[i++] = *pushback;
  148.     state = ('.' == c);
  149.     while(state != 6)
  150.     {
  151.         c = input_func();
  152.         buff[i++] = c;
  153.         if((BUFFLEN-1) <= i)
  154.             state = 5;
  155.  
  156.         switch(state)
  157.         {
  158.             /*
  159.                 In state 0, the function has seen no decimal points or
  160.                 exponents, just an initial string of numbers.
  161.             */
  162.             case 0:
  163.                 if(!isdigit(c))
  164.                 {
  165.                     if('.' == c)
  166.                         state = 2;
  167.                     else if('E' == toupper(c))
  168.                         state = 3;
  169.                     else
  170.                     {
  171.                         *pushback = c;
  172.                         state = 6;
  173.                     }
  174.                 }
  175.                 break;
  176.  
  177.             /*
  178.                 In state 1, the function saw an initial decimal point
  179.                 and it MUST see a digit in order for there to be no
  180.                 error.
  181.             */
  182.             case 1:
  183.                 if(isdigit(c))
  184.                     state = 2;
  185.                 else
  186.                 {
  187.                     *pushback = c;
  188.                     error = 1;
  189.                     state = 6;
  190.                 }
  191.  
  192.             /*
  193.                 In state 2, the function has seen a decimal point, but
  194.                 no exponent.
  195.             */
  196.             case 2:
  197.                 if(!isdigit(c))
  198.                 {
  199.                     if('E' == toupper(c))
  200.                         state = 3;
  201.                     else
  202.                     {
  203.                         *pushback = c;
  204.                         state = 6;
  205.                     }
  206.                 }
  207.                 break;
  208.  
  209.             /*
  210.                 In state 3, the function has seen an exponent, and needs
  211.                 to see either a digit or a + or a - or there's an error.
  212.             */
  213.             case 3:
  214.                 if(isdigit(c))
  215.                 {
  216.                     state = 5;
  217.                 }
  218.                 else if (('+' == c) || ('-' == c))
  219.                 {
  220.                     state = 4;
  221.                 }
  222.                 else
  223.                 {
  224.                     *pushback = c;
  225.                     error = 1;
  226.                     state = 6;
  227.                 }
  228.                 break;
  229.  
  230.             /*
  231.                 In state 4, the function has seen an exponent and
  232.                 a + or - and it needs to see a digit or there's an
  233.                 error
  234.             */
  235.             case 4:
  236.                 if(isdigit(c))
  237.                 {
  238.                     state = 5;
  239.                 }
  240.                 else
  241.                 {
  242.                     *pushback = c;
  243.                     error = 1;
  244.                     state = 6;
  245.                 }
  246.  
  247.                 break;
  248.  
  249.             /*
  250.                 In state 5, the function is looking for a trailing string
  251.                 of digits.
  252.             */
  253.             case 5:
  254.                 if(!isdigit(c))
  255.                 {
  256.                     *pushback = c;
  257.                     state = 6;
  258.                 }
  259.                 break;
  260.  
  261.             /*
  262.                 None of the other states are valid.  Flag an error if
  263.                 you see them. (State 6 doesn't get a case because it
  264.                 should be filtered out at the top of the loop.)
  265.             */
  266.             default:
  267.                 state = 6;
  268.                 error = 1;
  269.         }
  270.     }
  271.  
  272.     /* Now, convert the found string to a number */
  273.     buff[i] = 0;
  274.     if(!error)
  275.         *value = strtod(buff, NULL);
  276.  
  277.     return error;
  278. }
  279.  
  280.  
  281. /*
  282.  * This is the function that handles getting nonterminals or "tokens"
  283.  * as well as numbers.  Since all tokens are either numbers (which
  284.  * all begin with digits, strangely enough) or single characters, I don't
  285.  * go to a whole lot of trouble checking things.  Whitespace is ignored.
  286.  * If it sees a character it doesn't recognize, it returns the error
  287.  * token.
  288.  *
  289.  * One bit of wierdness:  The unary_flag indicates whether or not "+" and
  290.  * "-" represent unary operators or binary operators.  Since that is
  291.  * context-dependant, gettoken would otherwise have difficulty telling.
  292.  *
  293.  * gettoken() returns TRUE if an error occurred, else it returns FALSE.
  294.  * The token itself is returned in token.
  295.  */
  296. static int  gettoken(TOKEN *token, int unary_flag)
  297. {
  298. int     c;
  299. static int  pushback = 0;
  300.  
  301.     if(pushback)
  302.     {
  303.         c = pushback;
  304.     }
  305.     else
  306.     {
  307.         do
  308.         {
  309.             c = input_func();
  310.         } while(isspace(c));
  311.     }
  312.  
  313.     if(isdigit(c) || '.' == c)
  314.     {
  315.         pushback = c;
  316.         if(getnumber(&(token->value), &pushback))
  317.             token->type = ERROR;
  318.         else
  319.             token->type = NUMBER;
  320.  
  321.         pushback = isspace(pushback) ? 0 : pushback;
  322.     }
  323.     else
  324.     {
  325.         pushback = 0;
  326.         switch(c)
  327.         {
  328.             case '+':
  329.                 token->type = ((unary_flag) ? UNPLUS : PLUS);
  330.                 break;
  331.  
  332.             case '-':
  333.                 token->type = ((unary_flag) ? UNMINUS : MINUS);
  334.                 break;
  335.  
  336.             case '*':
  337.                 token->type = STAR;
  338.                 break;
  339.  
  340.             case '/':
  341.                 token->type = SLASH;
  342.                 break;
  343.  
  344.             case '^':
  345.                 token->type = POWER;
  346.                 break;
  347.  
  348.             case '(':
  349.                 token->type = LPAREN;
  350.                 break;
  351.  
  352.             case ')':
  353.                 token->type = RPAREN;
  354.                 break;
  355.  
  356.             default:
  357.                 token->type = ERROR;
  358.         }
  359.     }
  360.     return  ERROR == token->type;
  361. }
  362.  
  363. /*
  364.  * This is the function that handles the value nonterminal.  It does
  365.  * unary operators, parentheses, and getting numbers.  In fact, this
  366.  * function is the one that gets most of the tokens from the list.
  367.  */
  368.  
  369. static void value(TOKEN *out)
  370. {
  371. TOKEN   in;
  372.  
  373.     gettoken(out, TRUE);
  374.     if(ISUNARY(out->type))
  375.     {
  376.         value(&in);
  377.         if(!ISNUMBER(in.type))
  378.         {
  379.             errortype = EV_BADVAL;
  380.             longjmp(error, 1);
  381.         }
  382.         out->value = (UNMINUS == out->type) ? -1 * in.value : in.value;
  383.         out->type = NUMBER;
  384.     }
  385.     else if(ISPAREN(out->type))
  386.     {
  387.         expression(out);
  388.         if(!ISNUMBER(out->type))
  389.         {
  390.             errortype = EV_BADEXP;
  391.             longjmp(error, 1);
  392.         }
  393.  
  394.         if(RPAREN != old_token.type)
  395.         {
  396.             errortype = EV_BADPAREN;
  397.             longjmp(error, 1);                  /* error */
  398.         }
  399.     }
  400.     else if(!ISNUMBER(out->type))
  401.     {
  402.         errortype = EV_BADPAREN;
  403.         longjmp(error, 1);                      /* error */
  404.     }
  405. }
  406.  
  407.  
  408. /*
  409.  * This function is the same as a pow() function, but it checks for
  410.  * overflow and domain errors before executing the calculation.
  411.  *
  412.  * NOTE:  This function is considerably more limited than C's pow()
  413.  * function.  src1 is not allowed to be negative even if src2 is an
  414.  * integer.  Also it will reject, as overflows, some calculations
  415.  * that would not overflow pow().  However, it will do most calcs
  416.  * properly.
  417.  */
  418. static int  bp_pow(double src1, double src2, double *dest)
  419. {
  420. int     exp1;
  421.  
  422.     if(0.0 > src1)
  423.         return TRUE;
  424.  
  425.     frexp(src1, &exp1);
  426.     if(DBL_MAX_EXP < fabs(src2 * exp1))
  427.         return TRUE;
  428.  
  429.     *dest = pow(src1, src2);
  430.     return FALSE;
  431. }
  432.  
  433. /*
  434.  * This is the function that handles the power nonterminal.  "Powers" are
  435.  * strings of values separated by "^"s.  Note that this function is
  436.  * recursive because strings of powers are normally evaluated right-to-left
  437.  * rather than the usual left to right.
  438.  */
  439.  
  440. static void power(TOKEN *out)
  441. {
  442. TOKEN   in1, in2;
  443.  
  444.     value(out);
  445.     if(!ISNUMBER(out->type))
  446.     {
  447.         errortype = EV_BADVAL;
  448.         longjmp(error, 1);
  449.     }
  450.  
  451.     gettoken(&in1, FALSE);
  452.     if(ISPOWER(in1.type))
  453.     {
  454.         power(&in2);
  455.         if(!ISNUMBER(out->type))
  456.         {
  457.             errortype = EV_BADPOW;
  458.             longjmp(error, 1);
  459.         }
  460.  
  461.         if(bp_pow(out->value, in2.value, &(out->value)))
  462.         {
  463.             errortype = EV_OVERFLOW;
  464.             longjmp(error, 1);
  465.         }
  466.  
  467.         out->type = NUMBER;
  468.     }
  469.     else
  470.         old_token = in1;
  471. }
  472.  
  473.  
  474. /*
  475.  * This function multiplies two numbers together, first checking them
  476.  * for overflow.  If the multiplication would overflow, TRUE is returned.
  477.  * Else, FALSE is returned and the product is returned in dest.
  478.  */
  479.  
  480. static int  bp_mul(double src1, double src2, double *dest)
  481. {
  482. int     exp1, exp2;
  483.  
  484.     frexp(src1, &exp1);
  485.     frexp(src2, &exp2);
  486.  
  487.     if(DBL_MAX_EXP < abs(exp1 + exp2))
  488.         return TRUE;
  489.  
  490.     *dest = src1 * src2;
  491.     return FALSE;
  492. }
  493.  
  494.  
  495. /*
  496.  * This function divides one number into another, first checking
  497.  * for overflow and division by zero.  If an error is detected, TRUE
  498.  * is returned.  Else, FALSE is returned and the result is returned
  499.  * in dest.
  500.  */
  501.  
  502. int     bp_div(double src1, double src2, double *dest)
  503. {
  504. int     exp1, exp2;
  505.  
  506.     frexp(src1, &exp1);
  507.     frexp(src2, &exp2);
  508.  
  509.     if((DBL_MAX_EXP < abs(exp1 - exp2)) || (0.0 == src2))
  510.         return TRUE;
  511.  
  512.     *dest = src1 / src2;
  513.     return FALSE;
  514. }
  515.  
  516. /*
  517.  * This function handles the factor nonterminal.  Factors are strings of
  518.  * powers separated by "/" and "*".
  519.  */
  520.  
  521. static void factor(TOKEN *out)
  522. {
  523. TOKEN   in;
  524. int     oldtype;
  525.  
  526.     power(out);
  527.     if(!ISNUMBER(out->type))
  528.     {
  529.         errortype = EV_BADPOW;
  530.         longjmp(error, 1);
  531.     }
  532.  
  533.     while(ISMULTOP(old_token.type))
  534.     {
  535.         oldtype = old_token.type;
  536.         power(&in);
  537.         if(!ISNUMBER(in.type))
  538.         {
  539.             errortype = EV_BADPOW;
  540.             longjmp(error, 1);
  541.         }
  542.  
  543.         if(STAR == oldtype)
  544.         {
  545.             if(bp_mul(out->value, in.value, &(out->value)))
  546.             {
  547.                 errortype = EV_OVERFLOW;
  548.                 longjmp(error, 1);
  549.             }
  550.         }
  551.         else
  552.         {
  553.             if(0.0 == in.value)
  554.             {
  555.                 errortype = EV_DIV0;
  556.                 longjmp(error, 1);
  557.             }
  558.  
  559.             if(bp_div(out->value, in.value, &(out->value)))
  560.             {
  561.                 errortype = EV_OVERFLOW;
  562.                 longjmp(error, 1);
  563.             }
  564.         }
  565.  
  566.         out->type = NUMBER;
  567.     }
  568. }
  569.  
  570.  
  571. /*
  572.  * This function handles the expression nonterminal.  Expressions are
  573.  * strings of factors separated by "+" and "-".  Addition and subtraction
  574.  * are not checked for overflow because I deem that it would be more
  575.  * trouble than it's worth.  If you know of a simple way to check an
  576.  * addition or subtraction for overflow, let me know.
  577.  */
  578.  
  579. static void expression(TOKEN *out)
  580. {
  581. TOKEN   in;
  582. int     oldtype;
  583.  
  584.     factor(out);
  585.     if(!ISNUMBER(out->type))
  586.     {
  587.         errortype = EV_BADFACT;
  588.         longjmp(error, 1);
  589.     }
  590.  
  591.     while(ISADDOP(old_token.type))
  592.     {
  593.         oldtype = old_token.type;
  594.         factor(&in);
  595.         if(!ISNUMBER(in.type))
  596.         {
  597.             errortype = EV_BADFACT;
  598.             longjmp(error, 1);
  599.         }
  600.  
  601.         out->value = (PLUS == oldtype) ?
  602.                 out->value + in.value : out->value - in.value;
  603.         out->type = NUMBER;
  604.     }
  605. }
  606.  
  607.  
  608. /*
  609.  * This is the main function for the evaluator.  The two parameters are
  610.  * a pointer to where the result should be stored and a pointer to the
  611.  * input function.  The input function can be literally anything that
  612.  * returns a single character every time it's called.  The example code
  613.  * contains an appropriate function for evaluating the expression
  614.  * stored in a string.
  615.  *
  616.  * This function returns an error code as defined in interp.h.
  617.  */
  618. int     eval(double *answer, int (*get_a_char)(void))
  619. {
  620. TOKEN   result;
  621.  
  622.     if(EV_RES_OK == setjmp(error))
  623.     {
  624.         input_func = get_a_char;
  625.         expression(&result);
  626.         if(ISNUMBER(result.type))
  627.         {
  628.             errortype = EV_RES_OK;
  629.             *answer = result.value;
  630.         }
  631.         else
  632.             errortype = EV_BADEXP;
  633.     }
  634.  
  635.     return errortype;
  636. }
  637.  
  638.  
  639. /* What follows is example/test code */
  640. #ifdef  DEBUG
  641. int     charcount;
  642. const char  *eval_string;
  643.  
  644.  
  645. /* This is the testing "input function" */
  646. static int  gchar()
  647. {
  648.     return eval_string[charcount++];
  649. }
  650.  
  651.  
  652. int     main()
  653. {
  654. char    buffer[100];
  655. double  result;
  656. int     errcode;
  657.  
  658.     fputs("What is the expression?  ", stdout);
  659.     fgets(buffer, 100, stdin);
  660.  
  661.     eval_string = buffer;
  662.     charcount = 0;
  663.     errcode = eval(&result, gchar);
  664.     if(errcode)
  665.         printf("Error: %s\n", EV_results[errcode]);
  666.     else
  667.         printf("\n\nThe result is: %f\n", result);
  668.     return(EXIT_SUCCESS);
  669. }
  670. #endif  /* DEBUG */
  671.